package com.zlk.algorithm.algorithm.dynamicPlan.knapsack073;

import java.io.*;

// 01背包(模版)
// 给定一个正数t，表示背包的容量
// 有m个货物，每个货物可以选择一次
// 每个货物有自己的体积costs[i]和价值values[i]
// 返回在不超过总容量的情况下，怎么挑选货物能达到价值最大
// 返回最大的价值
// 测试链接 : https://www.luogu.com.cn/problem/P1048
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的所有代码，并把主类名改成"Main"，可
// 以直接通过

// dp[i] = Math.max(dp[i-1],dp[i])
public class Code01_01Knapsack {


    /**
     * dp[i][j]含义 挑选到i位置货物不超过j的最大价值
     *
     * 可能性分析
     * 1、要i货物       dp[i][j] =dp[i-1][j-costs[i]]
     * 2、不要i货物     dp[i][j] = dp[i-1][j]
     *
     * @param m
     * @param t
     * @param costs
     * @param values
     */
    public int f(int m,int t,int[] costs,int[] values){
        int[][] dp = new int[m+1][t+1];
        //一个物品也没有的时候，都是0不用写
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= t; j++) {
                dp[i][j] = dp[i-1][j];
                if(j-costs[i-1]>=0){
                    dp[i][j] = Math.max(dp[i][j],dp[i-1][j-costs[i-1]]+values[i-1]);
                }
            }
        }
        return dp[m][t];
    }

    public int f2(int m,int t,int[] costs,int[] values){
       // int[][] dp = new int[m+1][t+1];
        int[] dp = new int[t+1];
        //一个物品也没有的时候，都是0不用写
        for (int i = 1; i <= m; i++) {
//            for (int j = t; j >= 0; j--) {
//                if(j-costs[i-1]>=0){
//                    dp[j] = Math.max(dp[j],dp[j-costs[i-1]]+values[i-1]);
//                }
//            }
            for (int j = t; j >=costs[i-1] ; j--) {
                dp[j] = Math.max(dp[j],dp[j - costs[i-1]] + values[i-1]);
            }
        }
        return dp[t];
    }

}
